Mathematics - Arithmetic and Base Conversions
Introduction ToDo Numeric Bases Most people know at least two different types of numeric bases, whether they know it or not. A numeric base, represents how many digits composed of the number system. Below is a following list of various numeric bases, with links to their related Wikipedia article for any additional information. Unary - Base 1 Binary - Base 2 Ternary - Base 3 Quaternary - Base 4 Quinary - Base 5 Senary - Base 6 Septenary - Base 7 Octal - Base 8 Nonary - Base 9 Denary - Base 10 Undecimal - Base 11 Duodecimal - Base 12 Tridecimal - Base 13 Tetradecimal - Base 14 Pentadecimal - Base 15 Hexadecimal - Base 16 Octadecimal - Base 18 Vigesimal - Base 20 Quadrovigesimal - Base 24 Hexavigesimal - Base 26 Septemvigesimal - Base 27 Trigesimal - Base 30 Base 36 Sexagesimal - Base 60 Base 64 Addition Addition is the most basic from of arithmetic and the most useful. With it, anyone or anything can do the other operations of arithmetic. Denary Addition Addition using the denary numbering system is what most people are used to and is also referred as base 10 or decimal. Oddly enough, this one of the more complicated bases to work with. I'm sure all of you know that the digits used in this system are 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Using the following truth table lets add 4 and 6 together. The result is a two digit number of 10, for now lets call the sum 0 and carry digit 1. Octal Addition The octal is a based 8 numbering system. As you could guess the digits used within this numbering system are 0, 1, 2, 3, 4, 5, 6, and 7. For an example let's add an octal 7 and 1 together. Since a denary 8 is past the limit of the octal system, the carry over value will be 1 and the sum will be 0. Like wise if we add 6 and 6 together, the result would be 14. Binary Addition There is a reason why computers like to work with binary, it's the easiest base to use. Binary or base 2, only has two digits to work with, 0 and 1. When we add a 0 and 1 together we only get one bit as the result. Likewise, when we add 1 and 1 together, the result is two bits. The sum of 1 + 1 is 0 and the carry bit is 1. Hexadecimal Addition Hexadecimal is a base 16 numbering system. The first question you might have is if we only have 10 digits in our Arabic numbering system, what do we use for the other five remaining digits? Well we make symbols for them, but the standard is to use a capital A through F. Case is important in this case, Normal when working with higher bases, lets say 64, the capital letters represent the digits ranging from 0 to 25. Lower case letters fill the ranges of 26 to 51 digits. Our Arabic digits fill the slots between 52 and 61 and the last two digits are reserved for '+' and '/'. Subtraction Subtraction is the a complementary form of addition. For example, another way of saying 4 - 2 could be (-2) + 4. One word of caution, computers has method of representing negative number. If you're bored, try playing around with the calculator on your computer. Denary Subtraction Hopefully, subtraction in the denary system doesn't cause too much difficulty for you. Octal Subtraction Binary Subtraction Hexadecimal Subtraction Multiplication Fans of counting multiplies of 9 with their hands, feel at easy. The same process works in the other bases. Let's skip ahead to octal multiplication for a second and look at as a sequence. n0 is 7 * 0 and n7 is 7 * 7. The answer of n0 of any base will the lowest digit, in this case n0 will equal 0. Likewise, n1 will be the highest available digit, 7. The following numbers in the sequence will follow the pattern of incrementing x and decrementing y. To reiterate, the rest of the sequence will follow the pattern of { n2 = 16, n3 = 25 ... n6 = 52, n7 = 61 }. I'll try pointing out a few other patterns they might come in handy as well. Denary Multiplication Octal Multiplication Values of 4 oscillates between 0 and 4, since 4 is halfway between 8 and 0. Binary Multiplication Hexadecimal Multiplication Values of 8 oscillates between 8 and 0 because 8 is halfway between 0 and 16. Division Substraction is complentary to addition, likewise, division is complementary to multiplication. Denary Division Octal Division Binary Division Hexadecimal Division ToDo Base Conversion ToDo Denary and Octal ToDo Denary and Binary Converting number between binary and denary is pretty easy to do and doesn't take much practice to pull of as long you can remember the powers of 2. Converting binary to decimal is more straight forward so let's try converting 10101010. To convert the prior binary number all you have to do is raised all the active bits to 2n. If you add together, 128, 32, 8, and 2 the answer should come out to be 170. Since additional and subtraction are complementary operations, you can use subtraction to convert decimal to binary. There is a reason why IBM settled on making a byte out of eight bits. Before the assembly language came into being, programs where written entirely out of 1's and 0's. As you could imagine, binary strings take up quite a bit of space with out for representing smaller values. To make writing and reading programs "slightly" more readable, machine language starting being written in hexadecimal. Let's take a quick look at the potential values of for bits, also called a nibble. The maximum amount of four bits can represent is 15 in denary, which is exactly how many digits are in hexadecimal numbering system. This makes conversion insanely easy. The binary string 1111 would be F in hexadecimal. Let's try quickly converting the byte, 1010 0101, into hexadecimal by breaking it into two nibbles to find out it's A5 in hexadecimal. Peano Arithmetic 'Axioms' Zero is consider a natural number For every natural number 'x' *'x' = 'x' *Reflexive For all natural numbers 'x' and 'y' *IF 'x' = 'y' *THEN 'y' = 'x' *Symmetric For all natural numbers 'x', 'y', and 'z' *IF 'x' = 'y' and 'y' = 'z' *THEN 'x' = 'z' *Transitive For all 'a' and 'b' *IF 'a' is a natural number and 'a' = 'b' *THEN 'b' is also a natural number For every natural number 'n' *'S(n)' is a natural number For every natural number 'n' *'S(n)' = 0 is false *No natural number whose successor is 0 For all natural numbers 'm' and 'n' *IF S(m) = S(n) *THEN 'm' = 'n' *S is an injection 'LISP Addition Example ' I probably wouldn't put together this page if it wasn't for sneaking in Peano Arithmetic. This form of arithmetic was discovered in the 19th century by the Italian mathematician Giuseppe Peano. A powerful wizard named Sussman describe Peano Arithmetic as working with two piles. One pile contains the current state of the problem, while the other pile contains what to add later to the other pile. I'm going to show you two nearly identical ways to do Peano Arithmetic and learn you a Lisp for great good. Here is a quick and dirty run down. The keyword define is used to create a symbol, the following examples, we are defining the operator '+' to add two numbers, x and y. If you have any programming experience think of it as overriding a default operator. The syntax of of Lisp is that the operator come first, then the operands. So in the following code samples, ( + x y ) is saying x + y. The codes also make use of an if statement and it might look somewhat odd. (if () ) For a chosen few, these examples might look very familiar. Let's call the following code, example A. What this version does when x = 0 the function returns the value of y, else x will equal the sum of the decrement of x and y will equal to the increment of y. Don't worry about following the code if you can't, hopefully you'll see it more clearly in a bit. Example A (define (+ x y) (if ( = x 0) y ( + (-1 + x) (1+ y) ) ) ) The next method is nearly identical to the first method, but the position where the incrementation changes. As in the following version, this version will return y if x is equal to 0. The change is the else part of the logic, the code will increment the sum of the decrement of x and y. Example B define (+ x y) (if ( = x 0) y ( 1+ (+ (-1 + x) y ) ) ) ) Alright, now lets clear up some confusion on how these methods differ. Let's look at how example A runs when trying to add the numbers 3 and 4. Example A takes 4 loops to add the numbers together. As you can see the values for x are gradually decreasing, while the values for y are increasing. Now lets look at example B to see how it takes this additional problem. What this version does is gradually decreases the value of x to 0 but instead of immediately adding the values to y, the program sets aside the increments to be handled later. Why is this useful to know? Well lets take a look at the structure of process. Both examples have a linear flow to them but Example B has a more complex bell-shaped curve it and takes about twice as long to find the value of 7. We can also judge the space and time complexity of these different versions using the big Θ notation. In both version the time it takes to complete the calculations is dependent on the size of the variable x. If x was 5, both methods would take longer compared to when x was 3. Knowing this, we can say both examples have a time complexity of Θ(x). When comparing the spacial complexity were these methods differ. Looking at example A, the method doesn't change shape as in example B so we can say example A has a space complexity of Θ(1) for remaining constant. Example B however has that strange bell-curve to consider. If you look at structure closely, you'll notice the amount of increments is dependent of the size of x so we could say that this example has a space complexity of Θ(x). I supposed I didn't fully answer why is it useful to know the structure of these two different methods. Another way of viewing these examples is that example A is a linear iterative process, while example B is a linear recursive process and that's something pretty useful to know about.